package com.xiaoyu.backtracking;

/**
 * @program: DS_and_A
 * @description:
 * 给定一个m x n 二维字符网格board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，
 * 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 * 输出：true
 *
 * @author: YuWenYi
 * @create: 2021-06-03 10:50
 **/
public class WordSearch_79 {
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}};
    private int rowLen;
    private int colLen;
    private int len;
    private boolean[][] visited;
    private char[] wordChars;
    private char[][] board;

    public boolean exist(char[][] board, String word) {
        rowLen = board.length;
        colLen = board[0].length;
        len = word.length();
        visited = new boolean[rowLen][colLen];
        wordChars = word.toCharArray();
        this.board = board;

        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                //对每一个位置都进行dfs深度遍历!
                if (dfs(i, j, 0)){  //只要有任意一个点进行dfs后返回true,那就说明找到了该字符串
                   return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int x, int y, int begin) {
        if (begin == len - 1){
            return wordChars[begin] == board[x][y];
        }

        if (wordChars[begin] == board[x][y]){  //只有对应字母相同,才有递归的资格!
            visited[x][y] = true;
            //变换方向,有四个方向可以变换,四个方向都试试!
            for (int[] direction : DIRECTIONS) {
                int x1 = x + direction[0];
                int y1 = y + direction[1];
                //如果移动后的结点还在图中,并且没有被访问过,那么就继续dfs
                if (inMap(x1, y1) && !visited[x1][y1]){
                    if(dfs(x1, y1, begin+1)){  //只要有一个搜索到了,就返回true
                        return true;
                    }
                }
            }
            //如果四个方向都试失败了,那么就回溯!
            visited[x][y] = false;
        }
        return false;
    }

    //结点是否在图中!
    private boolean inMap(int x, int y) {
        return x>=0 && x < rowLen && y>=0 && y < colLen;
    }

    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        WordSearch_79 search_79 = new WordSearch_79();
        System.out.println(search_79.exist(board, "SEE"));
    }
}
